﻿#define _CRT_SECURE_NO_WARNINGS 1
// 原题连接：https://www.luogu.com.cn/problem/P1226
/*
题目描述：
题目描述
给你三个整数
�
,
�
,
�
a,b,p，求
�
�
 
mod
 
�
a
b
 modp。

输入格式
输入只有一行三个整数，分别代表
�
,
�
,
�
a,b,p。

输出格式
输出一行一个字符串 a^b mod p=s，其中
�
,
�
,
�
a,b,p 分别为题目给定的值，
�
s 为运算结果。

输入输出样例
输入 #1复制
2 10 9
输出 #1复制
2^10 mod 9=7
说明/提示
样例解释

2
10
=
1024
2
10
 =1024，
1024
 
mod
 
9
=
7
1024mod9=7。

数据规模与约定

对于
100
%
100% 的数据，保证
0
≤
�
,
�
<
2
31
0≤a,b<2
31
 ，
�
+
�
>
0
a+b>0，
2
≤
�
<
2
31
2≤p<2
31
 。
*/

#include <iostream>
using namespace std;
int qmi(int a, int b, int p) {
    long long ret = 1;
    while (b > 0) {
        if (b & 1) {
            ret = (ret * a) % p;
        }
        a = (long long)a * a % p;
        b >>= 1;
    }
    return ret;
}
int main() {
    int a, b, p;
    scanf("%d%d%d", &a, &b, &p);
    printf("%d^%d mod %d=%d", a, b, p, qmi(a, b, p));
    return 0;
}